﻿namespace Algo.Sort
{
    using System.Collections.Generic;

    internal sealed class InsertsSortStrategy : ISortStrategy
    {
        private static readonly IDichotomySearchStrategy BinarySearchStrategy = AlgoFactory.CreateBinarySearchStrategy();

        public IEnumerable<T> Sort<T>(IEnumerable<T> items, IComparer<T> comparer, IAlgoExtensions extensions)
        {
            var list = new List<T>();
            foreach (var item in items)
            {
                int? prev;
                int? next;
                BinarySearchStrategy.Find(list, item, comparer, extensions, out prev, out next);
                if (next.HasValue)
                {
                    list.Insert(next.Value, item);
                }
                else
                {
                    list.Add(item);
                }
            }

            return list;
        }
    }
}